#pragma once
#include <algorithm>
#include <vector>
#include <random>
#include <iostream>
namespace STL
{
    size_t get_mid_index(std::vector<int> &sort_arr, size_t ind1, size_t ind2, size_t ind3)
    {
        if (sort_arr[ind1] > sort_arr[ind2] && sort_arr[ind1] > sort_arr[ind3])
        {
            return sort_arr[ind2] > sort_arr[ind3] ? ind2 : ind3;
        }
        else if (sort_arr[ind1] < sort_arr[ind2] && sort_arr[ind1] < sort_arr[ind3])
        {
            return sort_arr[ind2] < sort_arr[ind3] ? ind2 : ind3;
        }
        else
        {
            return ind1;
        }
    }
    void quick_sort(std::vector<int> &sort_arr, size_t left, size_t right) // 闭区间排序
    {
        if (right - left <= 1)
        {
            if (right - left == 1)
            {
                if (sort_arr[left] > sort_arr[right])
                    std::swap(sort_arr[right], sort_arr[left]);
            }
            return;
        }
        int mid = left + (right - left) / 2;
        size_t mid_ind = get_mid_index(sort_arr, left, mid, right);
        int refer_val = sort_arr[mid_ind];
        int small = left - 1, big = right + 1;
        int cur = left;
        for (; cur < big; cur++)
        {
            if (sort_arr[cur] < refer_val)
            {
                std::swap(sort_arr[++small], sort_arr[cur]);
            }
            else if (sort_arr[cur] > refer_val)
            {
                std::swap(sort_arr[--big], sort_arr[cur]);
                cur--;
            }
        }
        if (small != left - 1)
            quick_sort(sort_arr, left, small);
        if (big != right + 1)
            quick_sort(sort_arr, big, right);
    }

    int tmp[1000000] = {0};
    void merge_sort(std::vector<int> &sort_arr, size_t left, size_t right)
    {
        if (right - left <= 1)
        {
            if (right - left == 1)
            {
                if (sort_arr[left] > sort_arr[right])
                    std::swap(sort_arr[right], sort_arr[left]);
            }
            return;
        }
        int mid = left + (right - left) / 2;
        merge_sort(sort_arr, left, mid);
        merge_sort(sort_arr, mid + 1, right);
        int lindex = left, rindex = mid + 1;
        int n = 0;
        while (lindex <= mid && rindex <= right)
        {
            if (sort_arr[lindex] < sort_arr[rindex])
            {
                tmp[n++] = sort_arr[lindex++];
            }
            else
            {
                tmp[n++] = sort_arr[rindex++];
            }
        }
        while (lindex <= mid)
        {
            tmp[n++] = sort_arr[lindex++];
        }
        while (rindex <= right)
        {
            tmp[n++] = sort_arr[rindex++];
        }
        for (int i = left; i <= right; i++)
        {
            sort_arr[i] = tmp[i - left];
        }
    }

    int parent(int index)
    {
        return (index - 1) >> 1;
    }

    int leftchild(int index)
    {
        return (index << 1) + 1;
    }

    int rightchild(int index)
    {
        return (index << 1) + 2;
    }

    void down_update(std::vector<int> &sort_arr, int cur, int n) // n是闭区间下标
    {
        while (leftchild(cur) <= n)
        {
            int target = cur, left = leftchild(cur), right = rightchild(cur);
            if (sort_arr[target] < sort_arr[left])
                target = left;
            if (right <= n && sort_arr[target] < sort_arr[right])
                target = right;
            if (target == cur)
                break;
            std::swap(sort_arr[target], sort_arr[cur]);
            cur = target;
        }
    }

    void up_update(std::vector<int> &sort_arr, int start, int cur)
    {
        while (cur > start)
        {
            int parent_index = parent(cur);
            if (sort_arr[parent_index] < sort_arr[cur])
            {
                std::swap(sort_arr[parent_index], sort_arr[cur]);
                cur = parent_index;
            }
            else
                break;
        }
    }

    void heap_sort(std::vector<int> &sort_arr, size_t left, size_t right) // 闭区间
    {
        // 1. 建堆 - 从左往右逐个上浮（仍然不推荐，效率低）
        for (int i = left; i <= (size_t)right; i++)
        { // 从left+1开始
            up_update(sort_arr, left, i);
        }
        // int n = right - left + 1;
        // for (int i = left + n / 2 - 1; i >= (int)left; i--)
        // {
        //     down_update(sort_arr, i, right); // 从最后一个非叶子节点开始
        // }

        for (int i = left; i <= right; i++)
            std::cout << sort_arr[i] << " ";
        std::cout << std::endl;

        // 2、排序
        for (int i = right; i > left; i--)
        {
            std::swap(sort_arr[i], sort_arr[0]);
            down_update(sort_arr, 0, i - 1);
        }
    }

    void bubble_sort(std::vector<int> &sort_arr)
    {
        int n = sort_arr.size();
        for (int i = 0; i < n; i++)
        {
            bool target = false;
            for (int j = 0; j < n - i - 1; j++)
            {
                if (sort_arr[j] > sort_arr[j + 1])
                {
                    std::swap(sort_arr[j + 1], sort_arr[j]);
                    target = true;
                }
            }
            if (target == false)
                break;
        }
    }

    bool _check(std::vector<int> &nums)
    {
        for (size_t i = 0; i < nums.size() - 1; i++)
            if (nums[i] > nums[i + 1])
                return false;
        return true;
    }

    void check(std::vector<int> &nums)
    {
        bool ret = _check(nums);
        if (ret == false)
        {
            std::cout << "当前检测排序错误，请改正一下吧！" << std::endl;
        }
        else
        {
            std::cout << "兄弟，你真流弊！排序没有问题！" << std::endl;
        }
    }
}